package com.dq.tree;

import java.util.LinkedList;
import java.util.Random;

/**
 * @Author: Dang Qi
 * @Date: 2021/2/2  15:27
 * @Description:
 */
public class Tree {
    //默认树每个 val的最大值
    private static final int MAX_DEFALUT = 100;
    //默认树结点数
    private final static int N_DEFALUT = 8;
    //不产生节点的可能性
    private final static double NULL_POINT_DEFALUT = 0.07;
    //产生一个随机的树
    public static TreeNode proATree() {
        return proATree(MAX_DEFALUT,N_DEFALUT);
    }
    //nodeNumMax 节点最大值
    public static TreeNode proATree(int nodeNumMax) {
        return proATree(nodeNumMax,N_DEFALUT);
    }
    //max 节点最大值，n 节点数
    public static TreeNode proATree(int max,int n) {
        Random r = new Random();
        TreeNode root = new TreeNode(r.nextInt(max));
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int i=1;
        while(i<n &&!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(i<n&&Math.random()>NULL_POINT_DEFALUT) {
                node.left = new TreeNode(r.nextInt(max));
                queue.offer(node.left);
                i++;
            }
            if(i<n&&Math.random()>NULL_POINT_DEFALUT) {
                node.right = new TreeNode(r.nextInt(max));
                queue.offer(node.right);
                i++;
            }
        }
        return root;
    }
    public static TreeNode proATree(Integer []t) {
        if(t==null||t.length==0) return null;
        TreeNode root = newInstance(t[0]);
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        for(int i=1;i<t.length&&!queue.isEmpty();i++) {
            TreeNode node = queue.poll();
            node.left = newInstance(t[i++]);
            if(node.left!=null) queue.offer(node.left);
            if(i<t.length) {
                node.right = newInstance(t[i]);
                if(node.right!=null) queue.offer(node.right);
            }
        }
        return root;
    }

    //产生一颗完全二叉树
    public static TreeNode proATreeFull(int height) {
        return proATreeFull(height, 0);
    }

    public static TreeNode proATreeFull(int height, int tree_start) {

        if(height==0) return null;
        int num = (int)(Math.pow(2,height)-1)+tree_start;
        TreeNode root = new TreeNode(tree_start);
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        for(int i=tree_start+1;i<num&&!queue.isEmpty();i++) {
            TreeNode node = queue.poll();
            node.left = new TreeNode(i++);
            queue.offer(node.left);
            if(i<num) {
                node.right = new TreeNode(i);
                queue.offer(node.right);
            }
        }
        return root;
    }

    public static TreeNode newInstance(Integer val){
        return val == null ?null : new TreeNode(val);
    }

}
